//#define _CRT_SECURE_NO_WARNINGS 1
//
//
//
//
//
//
//
//
//
//#include <vector>
//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int n = prices.size();
//        int ret = -0x3f3f3f;
//        vector<vector<int>> f(n, vector<int>(3, -0x3f3f3f));
//        vector<vector<int>> g(n, vector<int>(3, -0x3f3f3f));
//        f[0][0] = -prices[0];
//        g[0][0] = 0;
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j < 3; j++) {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//                g[i][j] = g[i - 1][j];
//                if (j - 1 >= 0) {//>=0
//                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
//                }
//            }
//        }
//        for (int c = 0; c < 3; c++) {
//            ret = max(ret, g[n - 1][c]);
//        }
//        return ret;
//    }
//};
//
//
//
//
//
//
//
//
//
//#include <climits>
//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int prevmin = INT_MAX;
//        int n = prices.size();
//        int ret = INT_MIN;
//        for (int i = 0; i < n; i++)
//        {
//            prevmin = min(prices[i], prevmin);
//            ret = max(ret, prices[i] - prevmin);
//        }
//        return ret;
//    }
//};